101B - Buses - CodeForces Solution

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include "bits/stdc++.h"
using namespace std;
#define dbg(...)
using ll = int64_t;
#define space " | "
const ll inf = INT_MIN;
const ll MOD = 1e9 + 7;
 
inline ll add(ll a, ll b, ll mod = MOD) {
  a += b; return a >= mod ? a - mod : a;
}
inline ll sub(ll a, ll b, ll mod = MOD) {
  a -= b; return a < 0 ? a + mod : a;
}
inline ll mul(ll a, ll b, ll mod = MOD) {
  return ll((long long) a * b % mod);
}
inline ll power(ll base, long long ex, ll mod = MOD) {
  ll res = 1;
  for (; ex > 0; ex >>= 1) {
    if (ex & 1) res = mul(res, base, mod);
    base = mul(base, base, mod);
  }
  return res;
}
inline ll inv(ll a, ll mod = MOD) {
  return power(a, mod - 2, mod);
}
inline ll mdiv(ll a, ll b, ll mod = MOD) {
  return mul(a, power(b, mod - 2,  mod));
}
inline void adds(ll &a, ll b, ll mod = MOD) {
  a += b; if (a >= mod) a -= mod;
}
inline void subs(ll &a, ll b, ll mod = MOD) {
  a -= b; if (a < 0) a += mod;
}
inline void muls(ll &a, ll b, ll mod = MOD) {
  a = ll((long long) a * b % mod);
}
inline void mdivs(ll &a, ll b, ll mod = MOD) {
  a = mdiv(a, b, mod);
}
vector<ll> fact,ifact;
void prep_fact(ll mx = 1e5 + 40) {
  fact.assign(mx,0);
  ifact.assign(mx,0);
  fact[0] = 1;
  for (ll i = 1; i < mx; ++i) fact[i] = mul(i, fact[i - 1]);
  ifact[mx - 1] = inv(fact[mx - 1]);
  for (ll i = mx - 1; i > 0; --i) ifact[i - 1] = mul(i, ifact[i]);
}
inline ll ncr(ll n, ll r) {
  if (n < r || r < 0 || n < 0) return 0;
  return mul(fact[n], mul(ifact[n - r], ifact[r]));
}

const ll maxi = 2e5+1;
ll k=0;
long long tree[2*maxi];
 
long long query(ll l,ll r){
    long long ans=0;
    for (l+=k,r+=k; l < r; l>>=1 , r>>=1)
    {
        if(l&1){
            ans+=tree[l++];
            ans%=MOD;
        }
        if(!(r&1)){
            ans+=tree[r--];
            ans%=MOD;
        }
    }
    if(l==r){
        ans+=tree[l];
        ans%=MOD;
    }
    return ans;
    
}
 
void update(ll key,ll value){
    key = key+k;
    tree[key]+=value;
    tree[key]%=MOD;
    for (ll par = (key/2); par > 0; par>>=1)
    {
        // tree[par]-=change;
        tree[par]+=value;
        tree[par]%=MOD;
    }
}
bool sortbysec(const pair<ll,ll> &a,
              const pair<ll,ll> &b)
{
    return (a.second < b.second);
}


void Solution(ll number) {
    
    ll n,m;
    cin>>n>>m;
    map<ll,ll> mrr;
    ll u,v;
    vector<pair<ll,ll>> vrr;
    // vector<ll> uniques;
    set<ll> srr;
    for (ll i = 0; i < m; i++)
    {
      cin>>u>>v;
      vrr.push_back({u,v});
      srr.insert(u);
      srr.insert(v);
    }
    srr.insert(0);
    srr.insert(n);
    k = 0;
    for (auto &x : srr)
    {
      mrr[x]=k++;
    }
    

    sort(vrr.begin(),vrr.end(),sortbysec);


    tree[k] = 1;
    for (ll i = k - 1; i > 0; i--)
    {
        tree[i]=tree[(i<<1)]+tree[(i<<1)+1];
    }
    for (ll i = 0; i < m; i++)
    {
      ll u= mrr[vrr[i].first],v = mrr[vrr[i].second];
      ll sum = query(u,v-1);
      // cout<<u<<space<<v-1<<space<<sum<<endl;
      update(v,sum);
    }
    cout<<tree[2*k-1]<<endl;
    

    


    
    
    
}


int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\sethi\\Desktop\\Desktop\\competitive-programming\\input.txt", "r", stdin);
    freopen("C:\\Users\\sethi\\Desktop\\Desktop\\competitive-programming\\output.txt", "w", stdout);
#endif
    cout << fixed << setprecision(12);
    ll tc=1; 
    // cin >> tc; 
    // prep_fact();
	for (ll i = 0; i < tc; i++)
	{
		Solution(i+1);
	}
	
    
    cerr << "Time:" << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}